package 动态数组.队列;

import 动态数组.队列.接口.Deque;

import java.util.Iterator;

/**
 * 双端队列
 * @param <E>
 */
public class ArrayDeque<E> implements Deque<E> {
    private static int DEFAULT_CAPACITY = 10;
    private E[] data;
    //双端队列的队头指针
    private int front;
    //双端队列的队尾指针
    private int rear;
    //队列的实际元素的长度
    private int size;

    public ArrayDeque(){
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public void addFirst(E element) {
        if (isFull()){
            resize(data.length * 2 - 1);
        }
        front = (front - 1 + data.length) % data.length;
        data[front] = element;
        size++;
    }

    @Override
    public void addLast(E element) {
        if (isFull()){
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    public boolean isFull(){
        return (rear + 1) % data.length == front;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for (int i =front; i != rear ; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        front = 0;
        rear = index;
        data = newData;
    }

    @Override
    public E removeFirst() {
        if (isEmpty()){
            return null;
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (isShrink()){
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    private boolean isShrink() {
        return size == (data.length - 1) / 4 && (data.length - 1) > DEFAULT_CAPACITY;
    }

    @Override
    public E removeLast() {
        if (isEmpty()){
            return null;
        }
        rear = (rear - 1 + data.length) % data.length;
        E ret = data[rear];
        size--;
        if (isShrink()){
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E getFirst() {
        return data[front];
    }

    @Override
    public E getLast() {
        return data[(rear - 1) % data.length];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public void push(E element) {
        //左为栈底，右为栈顶
        addLast(element);
    }

    @Override
    public E peek() {
        return getLast();
    }

    @Override
    public E pop() {
        //左为栈底，右为栈顶
        return removeLast();
    }

    @Override
    public void offer(E element) {
        //左为队头，右为队尾
        addLast(element);
    }

    @Override
    public E poll() {
        return removeFirst();
    }

    @Override
    public E element() {
        return getFirst();
    }


    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()){
            sb.append(']');
        }else {
            for (int i = front; i != rear; i = (i + 1) % data.length) {
                sb.append(data[i]);
                if ((i + 1) % data.length == rear){
                    sb.append(']');
                }else {
                    sb.append(',');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null){
            return false;
        }
        if (this == obj){
            return true;
        }
        if (getClass() != obj.getClass()){
            return  false;
        }
        ArrayDeque other = (ArrayDeque) obj;
        if (size != other.size){
            return false;
        }else {
            int j = other.front;
            for (int i = front; i != rear; i = (i + 1) % data.length) {
                if(!data[i].equals(other.data[j])){
                    return false;
                }
                j = (j + 1) % other.data.length;
            }
            return true;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }

    class ArrayDequeIterator implements Iterator<E>{
        private int cur = front;
        @Override
        public boolean hasNext() {
            return front != rear;
        }

        @Override
        public E next() {
            E ret =  data[front];
            front = (front + 1) % data.length;
            return ret;
        }
    }
}
